#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_NUM 100
#define FLAG -100

typedef char Datatype;
typedef enum bool Bool;
enum bool {
        false, true
};

struct Node {
        Datatype val;
        struct Node *next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;

struct LinkStack {
        LinkList top;
        int len;
        int MAXNUM;
};
typedef struct LinkStack *PLinkStack;

PLinkStack createEmptyStack_link(void);
Bool isEmptyStack_link(PLinkStack plstack);
Bool Stack_is_full(PLinkStack plstack);
void push_link(PLinkStack plstack, Datatype x);
void pop_link(PLinkStack plstack);
Datatype top_link(PLinkStack plstack);
Bool is_Valid_Parentheses(char *s);
void destroy_LinkStack_2(PLinkStack S);

// 注意：我们的链栈没有头结点.
PLinkStack createEmptyStack_link(void)
{
        PLinkStack plstack = (PLinkStack)malloc(sizeof(struct LinkStack));
        plstack->top = NULL;
        plstack->len = 0;
        plstack->MAXNUM = MAX_NUM;
        return plstack;
}

Bool isEmptyStack_link(PLinkStack plstack)
{
        return plstack->top     == NULL;
}

Bool Stack_is_full(PLinkStack plstack)
{
        return plstack->len >= plstack->MAXNUM;
}

// 在栈顶头结点下面开始插入元素.
void push_link(PLinkStack plstack, Datatype x)
{
        // 入栈，首先判断栈是否满.
        if (Stack_is_full(plstack)) {
                printf("The Stack is full! Can't push element now!\n");
                return ;
        }
        // 不满就开辟新结点，插入之.
        PNode p = (PNode)malloc(sizeof(struct Node));
        p->val = x;
        // 先立新，再破旧.
        p->next = plstack->top;
        plstack->top = p;
}

Datatype top_link(PLinkStack plstack)
{
        if (!plstack->top) return -100;
        return plstack->top->val;
}

// 虽然进行了pop操作，但top指针依然指向链表的第一个元素，因为我们采用的是头插法和头删法.
void pop_link(PLinkStack plstack)
{
        if (isEmptyStack_link(plstack)) {
                printf("Now the stack is empty! Can't pop!\n");
                return ;
        }
        PNode tmp = plstack->top;
        plstack->top = plstack->top->next;
        free(tmp);
}

void print_Stack(PLinkStack S)
{
        if (isEmptyStack_link(S)) {
                printf("Now the stack is empty!\n");
                return ;
        }
        PNode p;
        for (p = S->top; p != NULL; p = p->next) {
                printf("%d ", p->val);
        }
        printf("\n");
}

Bool is_Valid_Parentheses(char *s)
{
        PLinkStack S = createEmptyStack_link();
        char *p = s;
        while (*p != '\0') {
                switch (*p) {
                        case '(':
                                push_link(S, *p);
                                break;
                        case '[':
                                push_link(S, *p);
                                break;
                        case '{':
                                push_link(S, *p);
                                break;
                        case ')':
                                if (isEmptyStack_link(S)) {
                                        destroy_LinkStack_2(S);
                                        return false;
                                } else {
                                        if ('(' == top_link(S)) {
                                                pop_link(S);
                                        } else {
                                                destroy_LinkStack_2(S);
                                                return false;
                                        }
                                }
                                break;
                        case ']':
                                if (isEmptyStack_link(S)) {
                                        destroy_LinkStack_2(S);
                                        return false;
                                } else {
                                        if ('[' == top_link(S)) {
                                                pop_link(S);
                                        } else {
                                                destroy_LinkStack_2(S);
                                                return false;
                                        }
                                }
                                break;
                        case '}':
                                if (isEmptyStack_link(S)) {
                                        destroy_LinkStack_2(S);
                                        return false;
                                } else {
                                        if ('{' == top_link(S)) {
                                                pop_link(S);
                                        } else {
                                                destroy_LinkStack_2(S);
                                                return false;
                                        }
                                }
                                break;
                }
                p++;
        }
        if (isEmptyStack_link(S)) {
                destroy_LinkStack_2(S);
                return true;
        } else {
                destroy_LinkStack_2(S);
                return false;
        }
}

void destroy_LinkStack_2(PLinkStack S)
{
        if (isEmptyStack_link(S)) {
                free(S);
                return ;
        }
        PNode q;
        PNode tmp;
        q = S->top;
        while (q->next != NULL) {
                tmp = q->next;
                free(q);
                q = tmp;
        }
        free(q);
        free(S);
}

int main()
{
        char *s = (char *)calloc(MAX_NUM + 1, sizeof(char));
        if (s == NULL) {
                printf("Out of memory!Can't calloc an array!\n");
                return 1;
        }
        gets(s);
        if (is_Valid_Parentheses(s)) {
                printf("It's a Valid Parentheses.\n");
        } else {
                printf("It's not a Valid Parentheses.\n");
        }
        free(s);
        return 0;
}
